/*
 * AP(r) Computer Science GridWorld Case Study:
 * Copyright(c) 2002-2006 College Entrance Examination Board
 * (http://www.collegeboard.com).
 *
 * This code is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * @author Alyce Brady
 * @author APCS Development Committee
 * @author Cay Horstmann
 */

import info.gridworld.grid.AbstractGrid;
import info.gridworld.grid.Location;

import java.util.ArrayList;

/**
 * A <code>BoundedGrid</code> is a rectangular grid with a finite number of
 * rows and columns. <br />
 * The implementation of this class is testable on the AP CS AB exam.
 */
public class SparseBoundedGrid<E> extends AbstractGrid<E> {
    private SparseGridNode[] occupantArray; // the array storing the grid elements
    private int numCols;
    private int numRows;

    /**
     * Constructs an empty bounded grid with the given dimensions.
     * (Precondition: <code>rows > 0</code> and <code>cols > 0</code>.)
     *
     * @param rows number of rows in BoundedGrid
     * @param cols number of columns in BoundedGrid
     */
    public SparseBoundedGrid(int rows, int cols) {
        if (rows <= 0)
            throw new IllegalArgumentException("rows <= 0");
        if (cols <= 0)
            throw new IllegalArgumentException("cols <= 0");
        numRows = rows;
        numCols = cols;
        occupantArray = new SparseGridNode[rows];
    }

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        // Note: according to the constructor precondition, numRows() > 0, so
        // theGrid[0] is non-null.
        return numCols;
    }

    public boolean isValid(Location loc) {
        return 0 <= loc.getRow() && loc.getRow() < getNumRows()
                && 0 <= loc.getCol() && loc.getCol() < getNumCols();
    }

    public ArrayList<Location> getOccupiedLocations() {
        ArrayList<Location> theLocations = new ArrayList<Location>();

        // Look at all grid locations.
        for (int r = 0; r < getNumRows(); r++) {
            SparseGridNode p = occupantArray[r];//p, the head of the linked list
            while (p != null) {
                Location tmp = new Location(r, p.getCol());//get exact location
                theLocations.add(tmp);
                p = p.getNext();
            }
        }
        return theLocations;
    }

    public E get(Location loc) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        SparseGridNode p = occupantArray[loc.getRow()];
        while (p != null) {
            if (loc.getCol() == p.getCol()) {
                return (E) p.getOccupant();
            }
            p = p.getNext();
        }
        return null;
    }

    public E put(Location loc, E obj) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        if (obj == null)
            throw new NullPointerException("obj == null");

        // remove the old obj
        E oldOccupant = remove(loc);
        SparseGridNode p = occupantArray[loc.getRow()];
        // put a new one in
        occupantArray[loc.getRow()] = new SparseGridNode(obj, loc.getCol(), p);
        return oldOccupant;
    }

    public E remove(Location loc) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");

        E obj = get(loc);
        if (obj == null) return null;

        SparseGridNode p = occupantArray[loc.getRow()];
        if (p != null) {
            if (p.getCol() == loc.getCol()) {
                occupantArray[loc.getRow()] = p.getNext();
            } else {
                SparseGridNode q = p.getNext();
                while (q != null && q.getCol() != loc.getCol()) {
                    p = p.getNext();
                    q = q.getNext();
                }
                if (q != null) p.setNext(q.getNext());
            }
        }

        return obj;
    }
}
